1. Field of the Invention
The present invention relates to link-state data stored at a router for supporting shortest path first routing of data packets across a network, and in particular to techniques for optionally excluding a directly connected router from the adjacent link-state data stored at a router.
2. Description of the Related Art
Networks of general purpose computer systems connected by external communication links are well known and widely used in commerce. The networks often include one or more network devices that facilitate the passage of information between the computer systems. A network node is a network device or computer system connected by the communication links.
Communications between nodes are typically effected by exchanging discrete packets of data. Information is exchanged within data packets according to one or more of many well known, new or still developing protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other based on information sent over the communication links. Each packet typically comprises 1] header information associated with a particular protocol, and 2] payload information that follows the header information and contains information that may be processed independently of that particular protocol. In some protocols, the packet includes 3] trailer information following the payload and indicating the end of the payload information. The header includes information such as the source of the packet, its destination, the length of the payload, and other properties used by the protocol. Often, the data in the payload for the particular protocol includes a header and payload for a different protocol associated with a different layer of detail for information exchange. The header for a particular protocol typically indicates a type for the next protocol contained in its payload. The higher layer protocol is said to be encapsulated in the lower layer protocol. The headers included in a packet traversing multiple heterogeneous networks, such as the Internet, typically include a physical (layer 1) header, a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The data-link header provides information defining a particular communication link between one network node and an adjacent node. The internetwork header provides information defining the source and destination address within the computer network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the end node assigned to the destination IP address stored in the packet's internetwork header. After each hop, the source or destination addresses in the packet's data-link header may be updated, as necessary. However, the source and destination IP addresses typically remain unchanged as the packet is transferred from link to link in the network.
Routers and switches are network devices that determine which communication link or links to employ to support the progress of data packets through the network. A network node that determines which links to employ based on information in the internetwork header (layer 3) is called a router. Some protocols pass protocol-related information among two or more network nodes in special control packets that are communicated separately and which include a payload of information used by the protocol itself rather than a payload of data to be communicated for another application. These control packets and the processes at network nodes that utilize the control packets are said to be in another dimension, a “control plane,” distinct from the “data plane” dimension that includes the data packets with payloads for other applications.
A shortest path first (SPF) method (also known as the Dijkstra algorithm) is widely known in the art for routing IP data packets on some networks. This method is described in an Internet Engineering Task Force (IETF) Request For Comment (RFC) 2328, the entire contents of which are hereby incorporated by reference as if fully set forth herein. RFC 2328 is available at the ietf.org domain of the World Wide Web. The SPF method is a link-state method. A link-state method floods routing information to all nodes on the internetwork in a link-state protocol control plane data packet; however, each router sends only the portion of the routing information that describes the state of its own links. Link-state data indicates direct links between a network node that performs routing functions (a router) and a different router (e.g., links on the same network segment, which do not involve a third router). The link-state data also indicates other characteristics of those links, such as bandwidth and congestion. According to link-state methods, each router builds a model of the entire network in its routing tables based on the link-state data received from other routers in the same.
In a link-state protocol, two routers establish an adjacency relationship between them by first verifying direct two-way communication between them over the same network segment and then synchronizing their link-state databases. A link-state protocol is an example of a routing protocol, which only exchanges control plane messages used for routing data packets sent in a different routed protocol (e.g., IP). Once the adjacency relationship is established, the two routers are called peers. The peers announce their adjacency relationship in periodic messages to other nodes in the network. For example, in the Open Shortest Path First (OSPF) protocol, the adjacency relationships are advertised in “Hello” messages and Link-state Advertisement (LSA) messages sent within a partitioned area of a larger network. The adjacency relationships among peers are used in all shortest path first computations by all routers in the partitioned area of the larger network. During a reliable flooding stage, each router is required to ensure that each of its peers has received its link-state data through a mechanism that includes an acknowledgement message and, sometimes, a retransmission message. On multi-access network segments that include more than two routers, the OSPF protocol selects a designated router (DR). The DR is responsible for generating LSAs for the entire multi access network segment.
As a consequence, resources on each router and many other network nodes are consumed for each peer with which the router establishes or maintains an adjacency relationship. The resources consumed by the router include: memory to store the peer and the characteristics of the link with the peer; processor time to compute the SPF based, at least in part, on the adjacency with that peer; processor time and link bandwidth for sending, receiving and processing routing information involving the peer; and corrective messaging and processing iterations to ensure that the same solutions are obtained at all peers (network convergence).
Maintaining an adjacency relationship with a peer provides the benefit of reaching network nodes connected more directly to that peer than to the router itself. Additional peers provide redundant paths to some network nodes and thus provide increased network reliability.
Many link-state protocols require each router to establish an adjacency relationship with every other router to which it becomes directly connected on the same network segment. As the number and types of network nodes that communicate directly with a network node increase, network performance can deteriorate as ever more node resources are consumed to establish, maintain, and correct adjacency relationships. The problems are exacerbated as mobile, wireless routers frequently enter and leave direct communications with fixed routers and with each other. Numerous mobile routers forming a mobile ad hoc network (MANET) are already proposed and anticipated. In such MANETs, at least some routers are expected to become inundated with traffic and computations to establish the mandatory adjacency relationships and to re-compute routing tables based on frequent changes in the adjacency relationships. As a consequence, many link-state protocols are not sufficiently scalable to handle numerous mobile routers.
In one approach, the link-state protocol is modified to use periodic advertisements for new peers, rather than synchronization involving complete database exchange between peers. Neighbor discovery still occurs as in current link-state protocols, but the link-state data for the routing information is learned over time. For example, OSPFv2 Wireless Interface Type, described in RFC 2386, uses periodic advertisements to eliminate “the formation of full adjacencies on wireless interfaces . . . no database synchronization is performed.”
While this form of neighbor reduction is suitable for some purposes, OSPFv2 sill requires eventual adjacency for direct (two-way) links. This can still be a problem for a large number of wireless network nodes temporarily on two-way links with a network node.
Another disadvantage of this approach is that the route distribution mechanism is changed, because routes are learned over time instead of being distributed in reliable flooding. Therefore this approach is not backward compatible with earlier versions of the protocol.
Based on the foregoing, there is a clear need for techniques for establishing and maintaining link-state data and shortest path first routing that does not suffer the disadvantages of prior art approaches. In particular, there is a need for techniques that do not form an adjacency relationship with every node that comes into direct link with a network node and that are still backward compatible for route distribution.